#pragma once
#include <vector>
#include <string>
#include <algorithm>

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct HashFunc<std::string>
{
	// TODO: change to BKDR
	size_t operator()(const std::string& str)
	{
		size_t hash = 0;
		for (auto& ch : str)
			hash += ch;
		return hash;
	}
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = std::lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}


template<class T>
struct HashNode
{
	T			 _data;
	HashNode<T>* _next;

	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{
	}
};

template<class K, class T, class KeyOfT, class Hash>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HTIterator
{
	typedef HashNode<T> Node;
	typedef HashTable<K, T, KeyOfT, Hash> HT;
	typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

	Node* _node;
	const HT* _ht;

	HTIterator(Node* node, const HT* ht)
		:_node(node)
		, _ht(ht)
	{
	}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		if (_node->_next)
			_node = _node->_next;
		else
		{
			size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();
			++hashi;
			while (hashi != _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];
					break;
				}
				++hashi;
			}
			if (hashi == _ht->_tables.size())
				_node = nullptr;
		}
		return *this;
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};


template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	friend struct HTIterator;

	typedef HashNode<T> Node;
public:
	typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
	typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;

	// TODO
	HashTable(const HashTable&) = delete;
	HashTable& operator=(const HashTable&) = delete;

	Iterator Begin()
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
				return Iterator(_tables[i], this);
		}
		return End();
	}
	Iterator End()
	{
		return Iterator(nullptr, this);
	}

	ConstIterator Begin() const
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
				return ConstIterator(_tables[i], this);
		}
		return End();
	}
	ConstIterator End() const
	{
		return ConstIterator(nullptr, this);
	}

	HashTable()
		:_tables(__stl_next_prime(1), nullptr)
		, _n(0)
	{
	}

	~HashTable()
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
	}

	std::pair<Iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		auto it = Find(kot(data));
		if (it != End())
			return { it,false };
		Hash hs;
		if (_n == _tables.size())
		{
			std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					size_t hashi = hs(kot(cur->_data)) % newtables.size();
					cur->_next = newtables[hashi];
					newtables[hashi] = cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
			_tables.swap(newtables);
		}
		size_t hashi = hs(kot(data)) % _tables.size();
		Node* newNode = new Node(data);
		newNode->_next = _tables[hashi];
		_tables[hashi] = newNode;
		++_n;
		return { Iterator(newNode, this),true };
	}

	Iterator Find(const K& key)
	{
		KeyOfT kot;
		Hash hs;
		size_t hashi = hs(key) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
				return { cur,this };
			cur = cur->_next;
		}
		return End();
	}

	bool Erase(const K& key)
	{
		KeyOfT kot;
		Hash hs;
		size_t hashi = hs(key) % _tables.size();
		Node* prev = nullptr;
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				if (prev == nullptr)
					_tables[hashi] = cur->_next;
				else
					prev->_next = cur->_next;
				delete cur;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}

private:
	std::vector<Node*> _tables;
	size_t _n = 0;
};